package com.shiyi.design.iterator;

import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * @author wangzhanshuai
 * @date 2021/2/5 6:55 下午
 * @since 1.0
 */
public class LinkedListImpl<E> implements ListInterface<E> {

    private int size;

    private Node<E> first;

    private Node<E> last;


    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }

    @Override
    public void add(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public IteratorInterface<E> iterator() {
        return new LinkedListIteratorImpl(0);
    }

    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    private class LinkedListIteratorImpl implements IteratorInterface<E> {

        private int modCount;

        private Node<E> next;

        private Node<E> lastReturned;

        @Override
        public boolean hasNext() {
            return modCount < size;
        }

        LinkedListIteratorImpl(int index) {
            next = (index == size) ? null : node(index);
            modCount = index;
        }

        @Override
        public E next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            modCount++;
            return lastReturned.item;
        }
    }

}
